package com.le.enhance.class8;

import org.junit.Test;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 排成一条线的纸牌博弈问题
 * 【题目】
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线。
 * 玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。
 * 请返回最后获胜者的分数。
 */
public class Code_03_CardsInLine {

    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return Math.max(first(arr, 0, arr.length - 1), last(arr, 0, arr.length - 1));
    }

    // 先手玩家
    public static int first(int[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        return Math.max(
                arr[i] + last(arr, i + 1, j),
                arr[j] + last(arr, i, j - 1)
        );
    }

    // 后手玩家
    public static int last(int[] arr, int i, int j) {
        if (i == j) {
            return 0;
        }
        return Math.min(
                first(arr, i + 1, j),
                first(arr, i, j - 1)
        );
    }

    public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[][] f = new int[arr.length][arr.length];
        int[][] s = new int[arr.length][arr.length];
        for (int j = 0; j < arr.length; j++) {
            // 打印f对角线
            f[j][j] = arr[j];
            for (int i = j - 1; i > -1; i--) {
                f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
                s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
            }
        }
        return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
    }

    public static void printArray(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(Arrays.toString(arr[i]));
        }
    }

    @Test
    public void test() {
        int[] arr = {1, 2, 100, 4};
        System.out.println(win1(arr));
        System.out.println(win2(arr));
    }
}
